Count largest group

Time: O(NLogN); Space: O(N); easy

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits.

Return how many groups have the largest size.

Example 1:

Input: n = 13

Output: 4

Explanation:

  • There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9].

  • There are 4 groups with largest size.

Example 2:

Input: n = 2

Output: 2

Explanation:

  • There are 2 groups [1], [2] of size 1.

Example 3:

Input: n = 15

Output: 6

Example 4:

Input: n = 24

Output: 5

Notes:

  • 1 <= n <= 10^4

Hint:

  1. Count the digit sum for each integer in the range and find out the largest groups.

[1]:

import collections

class Solution1(object):
    def countLargestGroup(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = collections.Counter()

        for x in range(1, n+1):
            count[sum(map(int, str(x)))] += 1

        max_count = max(count.values())

        return sum(v == max_count for v in count.values())


[2]:

s = Solution1()
n = 13
assert s.countLargestGroup(n) == 4
n = 2
assert s.countLargestGroup(n) ==2
n = 15
assert s.countLargestGroup(n) ==6
n = 24
assert s.countLargestGroup(n) ==5